﻿#pragma once
#include "Index.h"

/**
 * 数值的整数次方
 *
 * 实现函数 double Power(double base, int exponent)，求base的exponent次方。
 * 注意：
 * 1.保证base和exponent不同时为0。
 * 2.不得使用库函数，同时不需要考虑大数问题
 * 3.有特殊判题，不用考虑小数点后面0的位数。
 * 数据范围：∣base∣≤100  ，∣exponent∣≤100  ,保证最终结果一定满足 ∣val∣≤10^4
 * 进阶：空间复杂度O(1)  ，时间复杂度O(n) 
 */
class IPowerOfNum
{
public:
	virtual double Power(double base, int exponent) = 0;
};

class PowerOfNum
{
public:
	class Solution:public IPowerOfNum
	{
	public:
		double Power(double base, int exponent) override
		{
			if (base == 0)
				return 0;

			if (exponent < 0)
				return 1.0 / powerInner(base, -exponent);
			else
				return powerInner(base, exponent);
		}
	private:
		double powerInner(double base,int exponent)
		{
			if (exponent == 0)
				return 1;

			const double half = powerInner(base, exponent >> 1);
			const double ret = (exponent & 1) ? half * half * base : half * half;
			
			return ret;
		}
	};
};